package 牛客_面试必刷.Month07.day10;

import java.util.ArrayList;
import java.util.List;

public class 输出二叉树的右视图 {
    int index = 0;//遍历前序数组
    int Treeheight = 0;
    List<Integer> list = new ArrayList<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here

        //首先构建一个二叉树
        TreeNode root = rebuildTree(xianxu,zhongxu,0,zhongxu.length);

        //然后准备求右视图
        solve(root,0);
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public void solve(TreeNode root,int height){
        if(root == null) return;
        if(height >= Treeheight){
            list.add(root.val);
            Treeheight++;
        }
        solve(root.right,height + 1);
        solve(root.left,height+1);
    }

    public TreeNode rebuildTree(int[] xianxu, int[] zhongxu,int left,int right){
        if(left >= right || index == xianxu.length) return null;
        int mid = left;
        while(mid < right){
            if(xianxu[index] == zhongxu[mid]) break;
            mid++;
        }
        int val = xianxu[index++];
        TreeNode root = new TreeNode(val);
        root.left = rebuildTree(xianxu,zhongxu,left,mid);
        root.right = rebuildTree(xianxu,zhongxu,mid+1,right);
        return root;
    }
}
